#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node* Create();

void Print( Node* head );

void Release ( Node* head );

Node* Delete ( Node* head, int num );

Node* Insert ( Node* head, int num );

int main ( int argc, char const *argv[] ) {
    int choice, num;
    Node* head;
    while (1) {
        printf("input choice:\n1  input\t2  delete\n3  insert\t4  exit\n5  print\n");
        scanf("%d",&choice);
        switch ( choice ) {
        case 1:
            head = Create();
            Print(head);
            break;
        case 2:
            printf("input number to delete:\n");
            scanf("%d",&num);
            head = Delete(head, num);
            printf("Node without %d:\n",num);
            Print(head);
            break;
        case 3:
            printf("input number to insert:\n");
            scanf("%d",&num);
            head = Insert(head, num);
            printf("Node with %d:\n",num);
            Print(head);
            break;
        case 4:
            Release(head);
            return 0;
        case 5:
            Print(head);
            break;
        default:
            printf("input again\n\n");
            break;
        }
    }
}

Node* Create() {
    Node* head, *tail, *p;
    int num;
    head = tail = NULL;
    printf("Please input, end with -9999:\n");
    scanf("%d",&num);
    while ( num != -9999 ) {
        p = ( Node* )malloc( sizeof(Node) );
        p->data = num;
        p->next = NULL;
        if ( NULL == head ) {
            head = p;
        } else {
            tail->next = p;
        }
        tail = p;
        scanf("%d",&num);
    }
    return head;
}

void Print( Node *head ) {
    Node *p;
    p = head;
    if ( NULL == head ) {
        printf("Node NULL\n");
    } else {
        printf("Node is following\n");
        while ( p != NULL ) {
            printf("%d ",p->data);
            p = p->next;
        }
    }
    printf("\n");
}

void Release ( Node * head ) {
    Node *p1, *p2;
    p1 = head;
    while ( p1 != NULL ) {
        p2 = p1;
        p1 = p1 -> next;
        free(p2);
    }
    printf("free success!\n");
}

Node *Delete ( Node *head, int num ) {
    Node *p1, *p2;
    if ( NULL == head ) {
        printf("Node NULL!\n");
        return head;
    }
    p1 = head;
    while ( p1 -> next && p1 -> data != num ) {
        p2 = p1;
        p1 = p1 -> next;
    }
    if ( p1 -> data == num ) {
        if ( head == p1 ) {
            head = p1 -> next;
        } else {
            p2 -> next = p1 -> next;
        }
        free(p1);
        printf("Delete Sucess!\n");
    } else {
        printf("Can't find %d\n",num);
    }
    return head;    
}

Node *Insert ( Node *head, int num ) {
    Node *p, *p1, *p2;
    p = ( Node * ) malloc ( sizeof(Node) );
    p->data = num;
    p->next = NULL;
    p1 = head;
    while ( p1 && p->data > p1->data ) {
        p2 = p1;
        p1 = p1->next;
    }
    if ( p1 == head ) {
        head = p;
    } else {
        p2->next = p;
    }
    p->next = p1;
    printf("Insert Suceess!\n");
    return head;
}